﻿#define  _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>

//有效的括号
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。

//typedef char STDatatype;
//
//typedef struct Stack
//{
//    STDatatype* a;
//    int top;
//    int capacity;
//
//}ST;
//
//void StackInit(ST* ps);
//
//void StackDestory(ST* ps);
//
//void StackPush(ST* ps, STDatatype x);
//void StackPop(ST* ps);
//
//STDatatype StackTop(ST* ps);
//
//int StackSize(ST* ps);
//
//bool StackEmpty(ST* ps);
//
//void StackInit(ST* ps)
//{
//    assert(ps);
//    ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
//    if (ps->a == NULL)
//    {
//        perror("malloc()");
//    }
//    ps->top = 0;
//    ps->capacity = 4;
//}
//
//void StackDestory(ST* ps)
//{
//    assert(ps);
//    free(ps->a);
//    ps->a = NULL;
//    ps->top = ps->capacity = 0;
//}
//
////入栈
//void StackPush(ST* ps, STDatatype x)
//{
//    assert(ps);
//    if (ps->capacity == ps->top)
//    {
//        STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * 2 * ps->capacity);
//        if (tmp == NULL)
//        {
//            perror("realloc()");
//            exit(-1);
//        }
//        else
//        {
//            ps->a = tmp;
//            ps->capacity *= 2;
//
//        }
//    }
//    ps->a[ps->top] = x;
//    ps->top++;
//}
////出栈
//void StackPop(ST* ps)
//{
//    assert(ps);
//    // 栈空了，调用Pop，直接中止程序报错
//    assert(ps->top > 0);
//    ps->top--;
//}
//
////返回栈顶元素
//STDatatype StackTop(ST* ps)
//{
//    assert(ps);
//    assert(ps->top > 0);
//
//    return ps->a[ps->top - 1];
//}
//
//int StackSize(ST* ps)
//{
//    assert(ps);
//
//    return ps->top;
//
//}
//
//bool StackEmpty(ST* ps)
//{
//    assert(ps);
//
//    return ps->top == 0;
//}
//bool isValid(char* s) {
//    ST st;
//    StackInit(&st);
//    while (*s != '\0')
//    {
//        switch (*s)
//        {
//        case '(':
//        case '[':
//        case '{':
//        {
//            StackPush(&st, *s);
//            ++s;
//            break;
//        }
//        case ')':
//        case ']':
//        case '}':
//        {
//            if (StackEmpty(&st))
//            {
//                StackDestory(&st);
//                return false;
//            }
//            char top = StackTop(&st);
//            StackPop(&st);
//            if (top == '[' && *s != ']'
//                || top == '(' && *s != ')'
//                || top == '{' && *s != '}')
//            {
//                StackDestory(&st);
//                return false;
//            }
//            else
//            {
//                ++s;
//
//            }
//            break;
//        }
//        default:
//            break;
//
//        }
//    }
//    bool ret = StackEmpty(&st);
//    StackDestory(&st);
//    return ret;
//}



//用队列实现栈 

//链接：https ://leetcode.cn/problems/implement-stack-using-queues


typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);

void QueueDestory(Queue* pq);

//队尾入
void QueuePush(Queue* pq, QDataType x);

//队头出
void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

int QueueSize(Queue* pq);

bool QueueEmpty(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc()");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	//1.1个
	//2.多个
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}
typedef struct {
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	if (ps == NULL)
	{
		perror("malloc()");
		exit(-1);
	}
	QueueInit(&ps->q1);
	QueueInit(&ps->q2);
	return ps;
}

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* emptyQ = &obj->q1;
	Queue* nonemptyQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ = &obj->q2;
		nonemptyQ = &obj->q1;
	}
	while (QueueSize(nonemptyQ) > 1)
	{
		QueuePush(emptyQ, QueueFront(nonemptyQ));
		QueuePop(nonemptyQ);
	}
	int top = QueueFront(nonemptyQ);
	QueuePop(nonemptyQ);
	return top;
}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	//同时为空返回true
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
}